1. The Field of the Invention
The field of the present invention is that of the proxy servers used in connection with accessing data over the World Wide Web (xe2x80x9cWWWxe2x80x9d) through the Internet or other Wide Area Network (xe2x80x9cWANxe2x80x9d). More particularly, the present invention involves an array of multiple proxy servers configured together to act as a single distributed cache of information identified through the use of Uniform Resource Locators (xe2x80x9cURLxe2x80x9d). Specifically, the invention treats the routing of a URL request received by one array member to the array member having the cached information associated with the URL.
2. Present State of the Art
Generally speaking, the concept of a xe2x80x9ccachexe2x80x9d or xe2x80x9ccachingxe2x80x9d as used in computer terminology and applications typically means making a more accessible copy of some piece of data for a performance advantage. For example, information that is cached is in many instances more accessible than it otherwise would be so that processing speed is increased since accessing the cached information is quicker.
Since having excess copies of data can create its own sort of overhead and because cache size is limited, data is not typically retained in a cache indefinitely and will eventually be overwritten after a certain amount of time if the cache is being fully utilized. This may occur according to a Leased Recently Used (xe2x80x9cLRUxe2x80x9d) algorithm, an expiration time, or any other relevant criteria for a particular application. Caching commonly exists at the microprocessor level with instruction and data caches so as to avoid excessive accessing of system RAM and may also exist elsewhere in a computer system or in a network of computer systems.
Another form of caching is commonly used in relation to accessing data or information over the WWW. A user having Internet access can directly receive a URL identified data object, such as a web page, and then display it locally on a browser. Each time the user receives such a data object, there is a delay as the Hyper Text Transport Protocol (xe2x80x9cHTTPxe2x80x9d) request travels across the Internet to the location identified by the URL and the destination server processing the URL request responds with the requested data object. Because the data object can be quite large, the time to access the data objects with the HTTP request and response creates a significant amount of information traveling over the Internet connection causing delays and excess overhead.
In some organizations, many of the same data objects are requested by the various users within the organization. It is therefore common to introduce a proxy server that will receive user access requests from a client application, such as a web browser. Referring to FIG. 1, the use of a proxy server acting as a cache is shown. A client application 20 will direct all URL requests to a proxy server 21 that will serve as a cache for any information (i.e., URL data objects) associated with the URL. Should the proxy server 21 not have the URL data object within its cache, it will, in turn, make access over the Internet 22 to the destination server found within the URL in order to place the data object into its cache and then respond to the client 20 URL request. Thereafter, should another client make a request to the proxy server 21, it can be serviced directly from the cache without necessary access over the Internet to the destination server found in the URL itself.
Note that the client 20 can be any software application capable of communicating or directing requests to the proxy server 21 using the HTTP protocol and would include other proxy servers, web browsers, Internet xe2x80x9cenabledxe2x80x9d applications, etc. Furthermore, HTTP requests contain a variety of information that can be used to xe2x80x9cforcexe2x80x9d the proxy server 21 to access the URL data object over the Internet in order to assure that the xe2x80x9cfreshestxe2x80x9d copy has been accessed. Such operation of proxy servers and their use as caches are generally know in the art for use in servicing IITTP requests.
It should be noted that the term URL may indicate either the address of where a data object is originally located and accessed, or the data object itself. To distinguish, a URL itself would be an address or location of the data object whereas a URL data object would be the actual web page file that is transmitted across the Internet to the client application. Though the appropriate usage is readily identifiable by context, efforts will be made throughout this application to distinguish between the two.
There are benefits of having a proxy server acting as a cache for URL data objects. One benefit is that for cached items, the total access time for a user is generally reduced since the connection between the client 20 and the proxy server 21 is typically over a Local Area Network (xe2x80x9cLANxe2x80x9d) rather than having to access the data object over the Internet or other Wide Area Network (xe2x80x9cWANxe2x80x9d). Another benefit is for security purposes so that an organization may have a xe2x80x9cfirewallxe2x80x9d to protect itself from unwanted outside penetration.
Larger corporations and other organizations may have many proxy servers servicing their needs. It becomes desirable in such situations to harness many proxy servers together as a single, logical distributed cache. Ideally, such a single distributed cache would have no duplication of URL data objects contained therein. Furthermore, a single distributed cache should have as little overhead as possible in servicing any given URL request that arrives at a member of the distributed cache. In other words, the actual URL data object may not be residing at the same server that originally receives the URL request and some form of forwarding, routing, or acquisition of the desired URL data object must occur in order to service that original URL request.
One attempt at creating a such a distributed cache is the Internet Cache Protocol (xe2x80x9cICPxe2x80x9d) that coordinates the activity of an xe2x80x9carrayxe2x80x9d of proxy servers. Though ICP allows an array of proxy servers to function as a distributed cache, it also has some drawbacks as will be explained hereafter.
Referring now to FIG. 2, the interaction of a client with a proxy server array is shown. In such an arrangement, a client 23 will contact one of the proxy servers in the array 24 in order to access URL data objects that are available over the Internet 25. Typically, a client 23 is assigned to a particular proxy server within the proxy server array 24 and may itself be a proxy server. Since the URL data object requested by a client may exist in a different proxy server than the one contacted, a mechanism or protocol is necessary for routing the URL request from the receiving proxy server to the appropriate proxy server, or in some other way service that URL request.
Referring now to FIG. 3, proxy server array that is organized and configured according to the ICP protocol is shown. In the example shown in FIG. 3, a client 26 will direct HTTP requests to an assigned proxy server 27 that is part of an ICP proxy server array 28. Assuming that a desired URL data object is contained in the distributed cache created by the ICP proxy server array 28 and located at the proxy server 29, a scenario illustrating the operation of ICP is now shown. This scenario will also illustrate a number of problems that make ICP a less than optimal way of creating a distributed cache.
The URL request will originate at the client 26 and be received by the proxy server 27 as indicated by arrow 30. After determining that the desired URL object does not reside at the proxy server 27 in its local cache storage, a query will be sent out to all proxy servers in the ICP proxy server array 28 as indicated by the query messages path 32. In turn, every other proxy server that receives the query will give a response back to the proxy server 27 as indicated by the response message path 34. Each individual response will indicate whether or not the specified URL data object resides at that particular responding proxy server. Note that more than one of the proxy servers in the ICP proxy server array 28 may contain a given URL data object.
For purposes of this example, it is assumed that only the proxy server 29 actually contains the data object and therefore the response from proxy server 29 to proxy server 27 would be the only response having an indication that the desired or requested URL data object exists thereon. Note that for an ICP proxy server array 28 of N proxy servers, that N-1 messages were sent out by the proxy server 27 querying for the existence of the URL data object and N-1 messages were sent back to or received by the proxy server 27 in response, thus creating a fair amount of network message traffic and usage of the overall network bandwidth.
Once the proxy server 27 knows where the desired URL data object is located, it will issue a request to get the object as indicated by the get path 36. Naturally, the proxy server will respond by sending the desired URL data object from the proxy server 29 to the proxy server 27 as indicated by the send object path 38. Now that the proxy server 27 has the desired URL data object, it can respond to the original URL request and return that data object to the client 26.
Cache storage redundancy can be seen since the proxy server 27 will also place the URL data object into its local cache such that the same URL data object now exists in both proxy server 27 and proxy server 29. Also, network usage overhead is significant since the total number of messages to allow the proxy server 27 the ability to service the original URL request for an ICP proxy server array 28 of N proxy servers is 2(N-1)+2 total data messages across the network.
Given the above scenario, a number of undesirable problems exhibit themselves almost immediately. First, by using a query-response scenario to contact all of the proxy servers in the ICP proxy server array, a significant amount of network resources may be consumed. Additionally, a natural consequence of the query-response scenario is that the larger the ICP proxy server array 28 becomes the greater the network overhead for each non-resident URL request, therefore adding a negative scalability component to operating an ICP server array. This means that each addition of another proxy server onto the array will in fact increase the amount of communication between the different proxy servers for all array members and for each request in order to resolve the correct location of a desired URL data object. Theoretically, there may exist an upper limit to the number of proxy servers that may be comfortably used in an ICP proxy server array 28.
Another problem is that multiple copies of the distributed cache URL data objects exist across the various proxy servers. In an extreme case, each proxy server of the ICP proxy server array 28 could become a redundant mirror of the other array members. It would be desirable to have only one copy of a URL data object existing in the entire distributed cache so that the distributed cache may be used to its full capacity.
Finally, adding or deleting proxy servers from the ICP proxy server array 28 may totally disrupt the distribution of URL data objects across the entire logical cache. In an extreme case, the distributed cache may be xe2x80x9cemptiedxe2x80x9d upon any addition or removal of a proxy server from a proxy server array.
What is needed is a truly distributed logical cache across an array of proxy servers where a given URL data object is contained therein at only one location so as to maximize cache capacity. Furthermore, what is needed is a way to access the correct proxy server within the logical distributed cache or array of proxy servers without making a query to each and every proxy server making up the array thereby allowing a request received at one proxy server to be directly routed to the correct proxy server, or alternatively, an acquisition of the desired URL data object from the correct proxy server quickly attained. Finally, what is needed is a way of gracefully migrating cached URL data objects between the different proxy servers as a result of additions or removals of proxy servers from the proxy server array making up the distributed cache that will not require the reorientation of all URL data objects in the cache.
It is an object of the present invention to allow a URL data object request made to a proxy server array to be laterally routed to the proxy server having the desired URL data object in one hop without making expensive query-response transactions with each and every proxy server in the array.
It is another object of the present invention to share array membership information between the array members so that such array member ship information may be deterministically processed, along with a requested URL, to indicate a particular proxy server assigned to have the desired URL data object and do so from any proxy server.
It is a further object of the present invention to provide a proxy server array having positive scalability so that very large numbers of proxy servers may be used to create the array.
It is another object of the present invention to utilize deterministic hashing algorithms to allow consistent and predictable identification of a proxy server to be assigned or have residing thereon a particular URL data object.
It is yet another object of the present invention to provide a proxy server array that has a minimal amount of cached URL data object redundancy amongst the local caches of the individual proxy servers making up the array.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
To achieve the foregoing objects, and in accordance with the invention as embodied and broadly described herein a method, computer program product, and system for lateral URL lookup within a distributed cache of URLs are provided. A proxy server array according to the present invention makes up a form of queryless distributed caching that reduces the extraneous network traffic associated with other forms of distributed caching, such as a ICP proxy server array.
Each proxy server has access to the entire array membership information stored in array membership list. This array membership list is periodically updated and reflects changes in array membership due to additions, removals, or temporary unavailability of the various proxy servers that make up the array. When changes have propagated through the proxy server array, all array membership lists at each proxy server will contain identical information.
When a proxy server receives a URL data object request, it uses the array membership list, the URL itself, and a deterministic hashing function to identify which array member should actually hold the URL data object in its local cache. The request may then be serviced by laterally accessing the desired data object from the correct proxy server without making expensive query-response transactions over the network. The hashing function operates so as to distribute the cached URL data objects evenly over the entire proxy server array without redundancy so as to more efficiently use the array capacity.
The proxy server identification mechanism works by computing a hash value for each server name found in the array membership list and a hash value for the requested URL. The URL hash value is combined with each member proxy server hash value to form a combined value. The proxy server associated with the highest of the combined values is identified as where the desired URL should reside in local cache. A load factor that assigns some proxy servers proportionately more URL data objects for the local cache is also incorporated in the creation of the combined hash values.
All information for making a determination as to the correct proxy server is completely available at a single proxy server receiving the URL request so that no external information is necessary. Furthermore, because of the propagation of array membership information between the proxy servers, it is the exact same information and will identify the exact same proxy server regardless of which proxy server originally receives the URL request.
These and other objects and features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.